import javax.jnlp.ClipboardService;
import java.util.*;

class MagicDictionary {
    Map<Integer,List<String>> map=null;
    public MagicDictionary() {
        map=new HashMap<>();
    }

    public void buildDict(String[] dictionary) {
        for(String str:dictionary){
            int len=str.length();
            List<String> list=map.getOrDefault(len,new ArrayList<>());
            list.add(str);
            map.put(len,list);
        }
    }

    public boolean search(String searchWord) {
        int len=searchWord.length();
        for(Map.Entry<Integer,List<String>> entry:map.entrySet()){
            if(entry.getKey()!=len){
                continue;
            }
            for(String str:entry.getValue()){
                if(str.equals(searchWord)){
                    continue;
                }
                int sum=0;
                for(int i=0;i<len;i++){
                    char ch1=searchWord.charAt(i);
                    char ch2=str.charAt(i);
                    if(ch1!=ch2){
                        sum++;
                    }
                }
                if(sum==1){
                    return true;
                }
            }
        }
        return false;
    }
}



























class MagicDictionary1 {
    Map<Integer,List<String>> map;
    /** Initialize your data structure here. */
    public MagicDictionary1() {
        map=new HashMap<>();
    }

    public void buildDict(String[] dictionary) {
        for(String str:dictionary){
            int len=str.length();
            List<String> list=map.getOrDefault(len,new ArrayList<>());
            list.add(str);
            map.put(len,list);
        }
    }

    public boolean search(String searchWord) {
        int len=searchWord.length();
        for(Map.Entry<Integer,List<String>> entry:map.entrySet()){
            if(entry.getKey()!=len){
                continue;
            }else{
                for(String str: entry.getValue()){
                    if(str.equals(searchWord)){
                        continue;
                    }
                    int sum=0;
                    for(int i=0;i<len;i++){
                        char ch1=searchWord.charAt(i);
                        char ch2=str.charAt(i);
                        if(ch1!=ch2){
                            sum++;
                        }
                    }
                    if(sum==1){
                        return true;
                    }
                }
            }
        }
        return false;
    }
}
















public class project {
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] arr=new int[12];
        for(String word:words){
            arr[find(word)]++;
        }
        for(int i=9;i>=0;i--){
            arr[i]+=arr[i+1];
        }
        int[] ret=new int[queries.length];
        for(int i=0;i<queries.length;i++){
            ret[i]=arr[find(queries[i])+1];
        }
        return ret;
    }
    public int find(String str){
        int sum=1;
        char ch=str.charAt(0);
        for(int i=1;i<str.length();i++){
            if(ch==str.charAt(i)){
                sum++;
            }else if(ch>str.charAt(i)){
                sum=1;
                ch=str.charAt(i);
            }
        }
        return sum;
    }





















    public List<List<Integer>> findWinners(int[][] matches) {
        List<List<Integer>> list=new ArrayList<>();
        int maxLen=0;
        for(int[] matche:matches){
            maxLen=Math.max(matche[0],maxLen);
            maxLen=Math.max(matche[1],maxLen);
        }
        int[] win=new int[maxLen+1];
        int[] loser=new int[maxLen+1];
        for(int[] matche:matches){
            win[matche[0]]++;
            loser[matche[1]]++;
        }
        List<Integer> winList=new ArrayList<>();
        List<Integer> loserList=new ArrayList<>();
        for(int i=0;i<=maxLen;i++){
            if(loser[i]==0&&win[i]>0){
                winList.add(i);
            }else if(loser[i]==1){
                loserList.add(i);
            }
        }
        list.add(winList);
        list.add(loserList);
        return list;
    }















    public int largestPalindrome(int n) {
        int[] arr={0,9,987,123,597,677,1218,877,475};
        return arr[n];
    }
}
